home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / Puz02 / hex3.c < prev    next >
C/C++ Source or Header  |  2000-06-28  |  3KB  |  135 lines
  1. /*
  2.  * hex.c : パズル「ヘックス」 15 パズルの変形バージョン
  3.  *
  4.  */
  5. /*
  6.    初期状態から一番手数のかかる状態を求める
  7.    ０が空き場所を表す
  8.  
  9.          １------２
  10.        ／  ＼  ／  ＼
  11.      ３------４------５
  12.        ＼  ／  ＼  ／ 
  13.          ６------０
  14.  
  15. 座標
  16.          ０------１
  17.        ／  ＼  ／  ＼
  18.      ２------３------４
  19.        ＼  ／  ＼  ／ 
  20.          ５------６
  21. */
  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25. #include <time.h>
  26.  
  27. #define TRUE  1
  28. #define FALSE 0
  29. #define SIZE  7
  30.  
  31. /* 最大の状態数 7! = 5040 */
  32. #define MAX_STATE 5040
  33.  
  34. /* 隣接リスト */
  35. const char adjacent[SIZE][7] = {
  36.   1, 2, 3, -1, -1, -1, -1,  /* 0 */
  37.   0, 3, 4, -1, -1, -1, -1,  /* 1 */
  38.   0, 3, 5, -1, -1, -1, -1,  /* 2 */
  39.   0, 1, 2,  4,  5,  6, -1,  /* 3 */
  40.   1, 3, 6, -1, -1, -1, -1,  /* 4 */
  41.   2, 3, 6, -1, -1, -1, -1,  /* 5 */
  42.   3, 4, 5, -1, -1, -1, -1   /* 6 */
  43. };
  44.  
  45. /* キュー */
  46. char state[MAX_STATE + 1][SIZE];     /* +1 はワーク領域 */
  47. char space_postion[MAX_STATE];
  48. char move[MAX_STATE];
  49.  
  50. /* 初期状態 */
  51. char init_state[SIZE] = {
  52.   1, 2, 3, 4, 5, 6, 0
  53. };
  54.  
  55. int count = 0;
  56.  
  57. /* 同じ状態があるか */
  58. int check_same_state( int n )
  59. {
  60.   int i;
  61.   for( i = 0; i < n; i++ ){
  62.     count++;
  63.     if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
  64.   }
  65.   return FALSE;
  66. }
  67.  
  68. /* 結果を出力 */
  69. void print_answer( int n )
  70. {
  71.   int m = move[n - 1], c = 0, i;
  72.   while( move[--n] == m ){
  73.     c++;
  74.     for( i = 0; i < SIZE; i++ ){
  75.       printf("%d ", state[n][i] );
  76.     }
  77.     printf("\n");
  78.   }
  79.   printf("最長手数 %d 手、総数 %d 個\n", m, c );
  80. }
  81.  
  82. void print_answer_all( int n )
  83. {
  84.   int i, j;
  85.   for( j = 0; j < n; j++ ){
  86.     printf("手数 %d : ", move[j] );
  87.     for( i = 0; i < SIZE; i++ ){
  88.       printf("%d ", state[j][i] );
  89.     }
  90.     printf("\n");
  91.   }
  92. }
  93.  
  94. /* 探索 */
  95. void search( void )
  96. {
  97.   int front = 0, rear = 1, i;
  98.   /* 初期化 */
  99.   memcpy( state[0], init_state, SIZE );
  100.   space_postion[0] = 6;
  101.   move[0] = 0;
  102.   while( front < rear ){
  103.     int s = space_postion[front];
  104.     int n;
  105.     for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
  106.       /* 状態をコピー */
  107.       memcpy( state[rear], state[front], SIZE );
  108.       /* 移動 */
  109.       state[rear][s] = state[rear][n];
  110.       state[rear][n] = 0;
  111.       if( !check_same_state( rear ) ){
  112.     /* 登録 */
  113.     space_postion[rear] = n;
  114.     move[rear] = move[front] + 1;
  115.     rear++;
  116.       }
  117.     }
  118.     front++;
  119.   }
  120.   print_answer( rear );
  121. }
  122.  
  123. int main()
  124. {
  125.   int start, end;
  126.   start = clock();
  127.   search();
  128.   end = clock();
  129.   printf("比較回数 %d 回、時間 %d \n", count, end - start );
  130.   return 0;
  131. }
  132.  
  133. /* end of file */
  134.  
  135.